package 插入排序;

public class InsertDemo {
    public static void main(String[] args) {
//插入排序:
//将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。
//遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。
          int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
          //找到插入元素的索引
        int star=-1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i+1]<arr[i])
            {
                star=i+1;
                break;
            }
        }
        //开始插入
        for (int i =star; i < arr.length; i++) {
            int j=i;
            while(j>0&&arr[j]<arr[j-1]){
                    int tmp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=tmp;
                    j--;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
